정보과학회 논문지 A : 시스템 및 이론
Current Result Document :
| 한글제목(Korean Title) |
속도 함수를 가지는 기계들에 이기적 에이전트 스케줄링 |
| 영문제목(English Title) |
Scheduling Selfish Agents on Machines with Speed Functions |
| 저자(Author) |
김재훈
Jae-Hoon Kim
|
| 원문수록처(Citation) |
VOL 35 NO. 09 PP. 0417 ~ 0420 (2008. 10) |
한글내용
(Korean Abstract) |
우리는 이기적이고 비협조적인 사용자들이 이용하는 시스템의 성능을 최적화하는 문제를 다룬다. 사용자들이 요구하는 작업들은 각각의 속도함수를 가지고 있는 기계들에 스케줄 된다. 여기서 속도함수는 기계에 할당된 작업량에 반비례한다. 시스템의 성능은 기계들이 할당된 작업들의 수행을 끝내는 완료시간의 최대값으로 평가한다.
이기적인 사용자들은 자신의 작업이 수행될 기계를 고를 수 있고 현재 가장 빠른 기계를 고른다. 그러나 이러한 스케줄은 시스템의 성능을 최적화하지 못한다. 사용자들의 이기적인 행동으로 발생되는 시스템의 성능 저하를 측정하는 기준으로서 Price of Anarchy(PoA)가 소개되었다[1]. 이것은 내쉬 평형의 비용과 최적의 비용의 비율로 정의된다. 이 논문에서 우리는 위 스케줄링 문제에 대한 PoA를 평가한다.
|
영문내용
(English Abstract) |
We consider the problem of optimizing the performance of a system shared by selfish non-cooperative users. In this problem, small jobs which the users request should be scheduled on a set of shared machines with their speed functions, each of which dependson the amount of jobs allocated on a machine. The performance of the system is measured by the maximum of the completion times when the machines complete the jobs allocated on them.
The selfish users can choose a machine on which their jobs are executed, and they choose the fastest machine. But it typically results in suboptimal system performance. The Price of Anarchy(PoA) was introduced as a measure of the performance degradation due to the user's selfish behavior[1]. The PoA is the worst-case ratio of the cost of a Nash equilibrium to the optimal cost. In this paper, we estimate the PoA for the above scheduling problem.
|
| 키워드(Keyword) |
스케줄링
이기적인 사용자
내쉬 평형
Price of Anarchy
scheduling
selfish users
Nash equilibrium
|
| 파일첨부 |
PDF 다운로드
|
